1. Field of the Invention
The present invention relates to a reduction processing method in which reduction is applied to a difference figure produced by overlaying an original geometric figure on a new geometric figure generated by applying graphics processing to the original figure, or produced by overlaying two new geometric figures generated by applying different processing operations to an original geometric figure, and the validity of the operation is verified based on the size of the remaining figure. The invention also relates to a computer readable storage medium having a program stored thereon for causing a computer to carry out the reduction processing.
2. Description of the Related Art
In geometrical processing such as LSI mask pattern processing, the following two verification methods are traditionally employed to verify the validity of the data generated by geometrical processing.
In the first verification method, as disclosed in Japanese Unexamined Patent Publication No. 8-160598, first a difference figure is obtained by overlaying an original geometric figure (design data) on a new geometric figure generated by applying a geometrical processing operation (for example, optical proximity correction) to the original figure, in other words, the two geometric figures are XORed to produce the difference figure. Then, verification is made based on the size of the difference figure; that is, if the difference figure is large, it is determined that a problem has occurred in the geometrical processing and there is an error in the new figure generated by the geometrical processing. On the other hand, if the difference figure is smaller than a specified value, then it is determined that no problem has occurred in the geometrical processing and, therefore, there is no error in the new figure generated by the geometrical processing, that is, the new figure is judged to be normal.
In the second verification method, different processing systems using different algorithms or procedures, though the purpose of processing is the same, are applied to the original geometric figure and, as is done in the first verification method, a difference figure between the two new geometric figures generated by the respective systems is obtained; then, verification is made based on the size of the difference figure, and if the difference figure is large, it is determined that there is a problem in one or the other of the geometrical processing systems, that is, there is an error in either one of the new figures. On the other hand, if the difference figure is smaller than a specified value, both of the new figures are judged to be normal.
As a means for determining whether the difference figure is large or small, generally, a reduction technique is employed that applies reduction to the difference figure. That is, after reduction with a suitable sizing amount is applied to the difference figure, if the difference figure disappears, it is determined that the difference figure is small; otherwise, it is determined that the difference figure is large.
The reduction process consists of an offsetting step, in which an imaginary straight line drawn on each side of a source figure acquired as a difference figure from two original geometric figures is translated (offset) inwardly of the source figure by a distance equal to a prescribed sizing amount and an offset figure is generated by joining the intersection points of the thus offset imaginary straight lines, and an ORing step, in which an OR operation is performed on the offset figure to generate a final offset figure.
Conceptually, reduction is a process for thinning the source geometric figure by an amount equal to a sizing amount. Accordingly, when reduction is applied to the source figure by making the sizing amount, also called the offset amount, larger than the size of the source figure, the source figure should in principle disappear. As a result, when applying reduction, for example, to a difference figure representing the difference between an original geometric figure and a geometric figure generated by processing the original geometric figure, if a suitable sizing amount is chosen that can allow for the error, the error between the two geometric figures can be determined.
When reduction is applied to the source figure, the source figure should disappear as a result of the processing, even if the sizing amount is larger than the source figure, but there are cases where even when an OR operation is applied to the offset figure after the offsetting step, an “inside-out side”, occurs and the source figure does not disappear.
The inside-out side will be described below. When the line segment joining one vertex of the source figure to the corresponding vertex of the offset figure is designated an offset line segment, there are cases where two adjacent offset line segments intersect each other. That the two adjacent offset lines intersect each other means that when one side of the source figure is offset by a distance equal to a sizing amount, this affects the slope of its adjacent side of the source figure and causes the orientation of the side of the offset figure to be reversed from the orientation of the corresponding side of the source figure. The one side of the offset figure at the ends of which these two offset line segments terminate is called the “inside-out side”.
As a result, there can occur cases where when the difference figure, i.e., the source figure, should disappear as a result of the reduction processing, and the result of the verification should be judged to be good, in actuality the source figure does not disappear because of the occurrence of the inside-out side and the result of the verification cannot be judged to be good.
To address this situation, various processing methods that can solve the problem caused by such an inside-out side have been proposed in the prior art. For example, in a first sizing processing method, the processing is performed by generating two offset points for each vertex of the source figure. When the vertex is one whose interior angle is smaller than 180°, for example, its two offset points consist of the point to which the vertex has been moved when one side associated with that vertex has been translated by a distance equal to the sizing amount, and the point to which the vertex has been moved when the other side associated with that vertex has been translated by the same distance. On the other hand, when the vertex is one whose interior angle is greater than 180°, its offset point is the point of intersection between an imaginary line translated by a distance equal to the sizing amount from one side associated with that vertex and an imaginary line translated by the same distance from the other side associated with that vertex.
In a second sizing processing method, a technique is employed that obtains a final offset figure by applying offset to each side of the source figure repetitively in small increments, because when each side of the source figure is offset in a single operation, an inside-out side occurs in the final offset figure.
However, of the above-described improved reduction processing methods, the first sizing processing method has the problem that it takes a long time for OR operations since the processing is performed by generating two new vertices for each vertex of the source figure.
On the other hand, the second sizing processing method has the problem that calculation errors contained in the final offset points (vertices of the offset figure) increase as the offset shape is obtained in a stepwise manner.
In view of the above situation, the present invention is aimed at solving the above problems and, in the reduction processing of the present invention, inside-out side elimination processing is applied to each inside-out side in the order of occurrence of the inside-out side in the offset figure. It is accordingly an object of the present invention to provide a reduction processing method that can reduce the amount of computation, is fast, and is capable of performing precise sizing.